Skip to main content

Delete Middle of Linked List

Problem​

Given a singly linked list, delete the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then linked list should be modified to 1->2->4->5. If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6. If the input linked list has a single node, then it should return NULL.

Examples​

Example 1:

Input:
LinkedList: 1->2->3->4->5
Output:
1 2 4 5

Example 2:

Input:
LinkedList: 2->4->6->7->5->1
Output:
2 4 6 5 1

Your Task​

The task is to complete the function deleteMid() which takes head of the linked list and returns head of the linked list with the middle element deleted. If the linked list is empty or contains a single element, then it should return NULL.

Expected Time Complexity: O(n)O(n)
Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 1≤n≤1051 ≤ n ≤ 10^5
  • 1≤value[i]≤1091 ≤ value[i] ≤ 10^9

Solution​

Intuition & Approach​

The simplest idea is to make two pointers, fast and slow. Increment the fast pointer by two steps and the slow pointer by one step until the fast pointer reaches the end of the linked list. By then, the slow pointer will have reached the exact middle of the list.

To delete the middle node, ensure that the slow pointer is at the node just before the middle. This can be done by starting the fast pointer from the second node instead of the first. Then, skip the middle node by changing the next pointer of the slow node to slow->next->next or slow.next.next.

Edge Case: If there is only one node in the linked list, return NULL or None.

Complexity​

  • Time Complexity: O(n)O(n)- Space Complexity: O(1)

Implementation​

class Solution:
def deleteMid(self, head):
if not head.next:
return None
slow, fast = head, head.next
while fast and fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
slow.next = slow.next.next
return head

Complexity​

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)

References​